<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /**
         * 打家劫舍题：
         * 输入：[1,2,3,1]
         * 输出：4
         * 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
         * 偷窃到的最高金额 = 1 + 3 = 4 。 
         * 
         * 思路：
         * 
        */
        /* 
            时间：O(2^n) 超出时间限制
            空间：O(n)
        */

        var rob = function(nums) {
            let max = 0
            function backTrack (index, sum) {
                // 退出条件
                if (index >= nums.length) {
                    // 修改更大值
                    max = Math.max(max, sum)
                    //再最后return的时候执行
                    return
                }
                // 偷当前房子
                backTrack(index + 2, sum + nums[index])
                // 不偷当前房子
                backTrack(index + 1, sum)
            }
            backTrack(0, 0)
            return max
        };
        // console.log(rob([2,7,9,3,1]));
        // console.log(rob([1,2,3,1]));
        // console.log(rob([1, 2])); // 出错1，
        // console.log(rob([1, 3, 1])); // 出错2
        console.log(rob([2,1,1,2])) // 出错3
        
    </script>
</body>

</html>